package com.zk.algorithm.bit;

import com.zk.algorithm.annotation.LeetCode;

/**
 * 两个元素出现一次，其它都出现两次
 *
 * 相同元素异或 = 0
 * 所有元素异或的结果 = 两个出现一次的元素异或 = diff
 * 按照 diff 最左边为 1 或者最右边为 1 就可以区分这两个数
 *
 * https://leetcode.com/problems/single-number-iii/discuss/68943/Examples-to-explain-the-XOR-solution-and-bit-manipulation-trick
 */
@LeetCode("260")
public class SingleNumber3 {

    public int[] singleNumber(int[] nums) {
        int result[] = new int[2];
        int xor = nums[0];
        for (int i = 1; i < nums.length; i++) {
            xor ^= nums[i];
        }

        int bit = xor & ~(xor - 1);
        int num1 = 0;
        int num2 = 0;

        for (int num : nums) {
            if ((num & bit) > 0) {
                num1 ^= num;
            } else {
                num2 ^= num;
            }
        }

        result[0] = num1;
        result[1] = num2;
        return result;
    }

}
